BOJ_2252_줄 세우기

위상 정렬(Topological Sorting)을 활용하는 문제

처음에 구현하기 간편한 깊이 우선 탐색(DFS) 방식으로 코드를 짰었는데,
런타임 에러가 나서 너비 우선 탐색(BFS)로 변경했다

런타임 에러가 난 이유?

파이썬에서 재귀의 깊이는 1000으로 제한되어 있다
이 문제의 경우 N <= 32000 이기 때문에
스택 오버플로우가 발생한 것이다

따라서 재귀 방식으로 하기 위해서는
sys.setrecursionlimit(숫자)
로 재귀의 깊이를 늘려주어야 한다

하지만 메모리나 시간 측면에서 bfs가 더 우수하기 때문에 bfs를 쓰는 것이 좋다

아래 : bfs / 위 : dfs

BFS 방식

import sys  
from collections import deque  
  
# 위상 정렬  
  
input = sys.stdin.readline  
  
N, M = map(int, input().split())  
graph = [list() for _ in range(N + 1)]  
degree = [0] * (N + 1)  
  
for _ in range(M):  
    start, end = map(int, input().split())  
    graph[start].append(end)  
    degree[end] += 1  
  
  
def bfs(graph):  
    queue = deque()  
  
    for i in range(1, N + 1):  
        if degree[i] == 0:  
            queue.append(i)  
            degree[i] = 0  
  
    res = []  
  
    while queue:  
        node = queue.popleft()  
        res.append(node)  
  
        for neighbor in graph[node]:  
            degree[neighbor] -= 1  
  
            if degree[neighbor] == 0:  
                queue.append(neighbor)  
  
    return res  
  
  
res = []  
  
if N == 1:  
    res.append(1)  
else:  
    res = bfs(graph)  
  
for i in res:  
    print(i, end=' ')

DFS 방식

# dfs로 구현한 것  
import sys  
from collections import deque  
  
input = sys.stdin.readline  
sys.setrecursionlimit(32001)  
  
N, M = map(int, input().split())  
graph = [[] for _ in range(N + 1)]  
  
for _ in range(M):  
    start, end = map(int, input().split())  
    graph[start].append(end)  
  
  
def dfs(node, visited, result):  
    visited[node] = True  
  
    for next_node in graph[node]:  
        if not visited[next_node]:  
            dfs(next_node, visited, result)  
  
    result.appendleft(node)
  
  
visited = [False] * (N + 1)  
result = deque()  

for i in range(1, N + 1):  
    if not visited[i]:  
        dfs(i, visited, result)  
  
for i in result:  
    print(i, end=' ')